// https://leetcode.cn/problems/permutations/
/*
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

*/

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
	// 最笨的回溯方法
    vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> res;
		vector<int> combine;
		int len = nums.size();
		unordered_map<int, int> um;
		combines(res, nums, combine, len, 0, len, um);
		return res;
    }
	
	void combines(vector<vector<int>> & res, vector<int>& nums, vector<int> combine, int height, int start, int len, unordered_map<int, int> um){
		if(height == 0){
			res.push_back(combine);
			return;
		}
		for(int i = start; i < start + len; i++){
			if(um.count(nums[i % len]) > 0){
				continue;
			}
			combine.push_back(nums[i % len]);
			um.insert({nums[i % len], 1});
			combines(res, nums, combine, height-1, start+1, len, um);
			combine.pop_back();
			um.erase(nums[i % len]);
		}
	}
	
	// 官方解法 swap
	vector<vector<int>> permute1(vector<int>& nums){
		vector<vector<int>> res;
		back(res, nums, 0, nums.size());
		return res;
	}
	
	void back(vector<vector<int>> & res, vector<int> & combine, int index, int len){
		if(index == len){
			res.push_back(combine);
			return;
		}
		for(int i = index; i < len; i++){
			cout << "i:" << i << " ,combine[i]:" << combine[i] << ",index:" << index << ", combine[index]:" << combine[index] << endl;
			swap(combine[i], combine[index]);
			back(res, combine, index+1, len);
			swap(combine[index], combine[i]);
		}
	}
};

int main(){
	Solution so;
	vector<int> s1 = {1,2,3};
	vector<vector<int>> a = so.permute1(s1);
	cout << "res:" << endl;
	for(auto items : a){
		for(auto item:items){
			cout << item << ",";
		}
		cout << endl;
	}
	return 0;
}